package 剑指offer.全排列;

import java.util.ArrayList;

/**
 * 输出 abc 的全排列
 */
public class 第38题字符串的排列 {

    public static ArrayList<String> Permutation(String str) {
        ArrayList<String> ans = new ArrayList<>();
        if (str == null || str.equals(""))
            return ans;
        char[] strs = str.toCharArray();
        boolean[] visited = new boolean[strs.length];
        arrange(strs, ans, visited, new StringBuffer());
        return ans;
    }

    private static void arrange(char[] strs,
                                      ArrayList<String> ans,
                                      boolean[] visited,
                                      StringBuffer buffer) {
        if (buffer.length() == strs.length) {
            // 去重
            if (!ans.contains(buffer.toString()))
                ans.add(buffer.toString());
            return;
        }
        for (int i = 0; i < strs.length; i++) {
            if (visited[i])
                continue;
            visited[i] = true;
            buffer.append(strs[i]);
            arrange(strs, ans, visited, buffer);
            visited[i] = false;
            buffer.delete(buffer.length()-1, buffer.length());
        }
    }

    public static void main(String[] args) {
        ArrayList<String> ans = Permutation("123");
        ans.forEach(x -> System.out.println(x));


    }
}
